Linux Multiprocessor Schedulers - Operating Systems: Virtualization, Concurrency & Persistence

Three different multiprocessor schedulers#

Interestingly, in the Linux community, no common solution has approached building a multiprocessor scheduler. Over time, three different schedulers arose: the O(1) scheduler, the Completely Fair Scheduler (CFS), and the BF Scheduler (BFS). See Meehean’s dissertation for an excellent overview of the strengths and weaknesses of said schedulers; here we just summarize a few of the basics.

Approaches used by the schedulers#

Both O(1) and CFS use multiple queues, whereas BFS uses a single queue, showing that both approaches can be successful. Of course, there are many other details which separate these schedulers. For example, the O(1) scheduler is a priority-based scheduler (similar to the MLFQ discussed before), changing a process’s priority over time and then scheduling those with the highest priority in order to meet various scheduling objectives; interactivity is a particular focus. CFS, in contrast, is a deterministic proportional-share approach (more like Stride scheduling, as discussed earlier). BFS, the only single-queue approach among the three, is also proportional-share, but based on a more complicated scheme known as Earliest Eligible Virtual Deadline First (EEVDF). Read more about these modern algorithms on your own; you should be able to understand how they work now!